#include <iostream>

using namespace std;


class linkquene
{
private:
    struct node {
        node(int data = -1) :data_(data),next(nullptr), prev(nullptr) {}
        int data_;
        node *next;
        node *prev;
    };
    int size_;
    node *head_;
public:
    linkquene();
    ~linkquene();
    bool isEmpty();
    // 入队
    void push(int data);
    // 出队
    void pop();
    // 获取队头元素
    int front();
    // 获取队尾元素
    int back();
    // 获取队列大小
    int que_size();
};

linkquene::linkquene()
{
    node *head = new node();
    head_ = head;
    head_->next = head_;
    head_->prev = head_;
    size_ = 0;
}

linkquene::~linkquene()
{
    node *p = head_->next;
    while (!p)
    {
        head_->next = p->next;
        p->next->prev = head_;
        delete p;
        p = head_->next;
    }
    delete head_;
    head_ = nullptr;
}

bool linkquene::isEmpty()
{
    return head_->next == head_;
}

void linkquene::push(int data)
{
    node *p = new node(data);
    p->next = head_;
    p->prev = head_->prev;
    head_->prev->next = p;
    head_->prev = p;
    size_++;
}

void linkquene::pop()
{
    // 队列判空
    if (isEmpty())
    {
        throw "queue is empty";
    }
    // 非空队列，从对头删除元素
    // 操作头结点的next 指针 以及第二个节点的prev指针，使其和对头元素连接
    node *p = head_->next;
    if (p)
    {
        head_->next = p->next;
        p->next->prev = head_;
    }
    
    // 释放第一个节点
    delete p;
    p = nullptr;
    size_--;
}

int linkquene::front()
{
    if (isEmpty())
    {
        throw "queue is empty";
    }
    return head_->next->data_;
}

int linkquene::back()
{
    if (isEmpty())
    {
        throw "queue is empty";
    }
    return head_->prev->data_;
}

int linkquene::que_size()
{
    return size_;
}


int main(int argc, const char** argv) {
    int arr[10] = {1,2,3,4,5,6,7,8,9,10};
    linkquene quene;
    for (int val : arr)
    {
        quene.push(val);
    }
    cout << "quene size: " << quene.que_size() << endl;

    while (!quene.isEmpty())
    {
        cout << quene.front() << " ";
        quene.pop();
    }
    cout << endl;
    quene.push(100);
    quene.push(120);
    cout << "quene size: " << quene.que_size() << endl;
    cout << "front: " << quene.front() << endl;
    cout << "back: " << quene.back() << endl;
    return 0;
}